package com.gitee.feizns.explore.data_structure.graph;

import com.gitee.feizns.explore.data_structure.graph.utils.UndirectedGraph;

import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Set;

/**
 * 1042. 不邻接植花
 * @author feizns
 * @since 2020/2/27
 */
public class GardenNoAdj {

    //    //4
    //    //[[1,2],[3,4],[3,2],[4,2],[1,4]]

    static int[][] data = { {3, 4}, {4, 2}, {3, 2}, {1, 3} };

    public static void main(String[] args) {
        System.out.println(Arrays.toString(gardenNoAdj(4, data)));
    }

    private static UndirectedGraph<Integer> graph;

    private static int[] ret;

    public static int[] gardenNoAdj(int N, int[][] paths) {
        ret = new int[N];
        graph = new UndirectedGraph();
        for (int[] path : paths)
            graph.addEdge(path[0], path[1]);

        for (int i = 0; i < N; i++) {
            Queue<Integer> queue = new LinkedList<>();
            queue.add(i + 1);
            while ( !queue.isEmpty() ) {
                Integer p = queue.poll();
                if ( ret[p - 1] == 0 )
                    ret[p - 1] = planting(p);
                Set<Integer> adj = graph.adj(p);
                adj.forEach(v -> { if ( ret[v - 1] == 0 ) queue.add(v); });
            }
        }
        return ret;
    }

    private static int planting(int k) {
        Set<Integer> adj = graph.adj(k);
        int[] tmp = new int[4];
        if ( ret[k - 1] != 0 )
            tmp[ret[k - 1] - 1] = 1;
        for (Integer v : adj) {
            if ( ret[v - 1] != 0 )
                tmp[ret[v - 1] - 1] = 1;
        }
        for (int i = 0; i < tmp.length; i++) {
            if ( tmp[i] == 0 )
                return i + 1;
        }
        //ignore.
        return -1;
    }

}
